// 131. 分割回文串
// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。
// 返回 s 所有可能的分割方案。

// 回文串 是正着读和反着读都一样的字符串。 

// 示例 1：

// 输入：s = "aab"
// 输出：[["a","a","b"],["aa","b"]]
// 思路：切割问题可以抽象为组合问题
// 如何模拟那些切割线  for循环 startIndex
// 切割问题中递归如何终止  切割线切到了字符串最后面，此时就是本层递归的终止终止条件。
// 在递归循环中如何截取子串 首先判断这个子串是不是回文，如果是回文，就加入在ans中
// 如何判断回文 使用双指针法，一个指针从前向后，一个指针从后先前，再判断是否相等
/**
 * @param {string} s
 * @return {string[][]}
 */
 var partition = function(s) {
    const res=[],ans=[];
    const backtracking=function(start){
        // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
        if(start>=s.length){
            res.push([...ans]);
            return;
        }
        const isPalindrome=function(s,start,a){
            for(let i=start,j=a;i<j;i++,j--){// 双指针法
                if(s[i]!==s[j]) return false;
            }
            return true;
        }
        
       for(let i=start;i<s.length;i++){
            if(isPalindrome(s,start,i)){// 是回文子串
                // 获取[startIndex,i]在s中的子串
                const str=s.substr(start,i-start+1);
                ans.push(str);
            }else continue;// 如果不是则直接跳过
            backtracking(i+1);// 寻找i+1为起始位置的子串
            ans.pop();// 回溯过程，弹出本次已经填在的子串
        }
        
    }
    backtracking(0);
    return res;
};